//
// Created by Administrator on 2021/8/10.

//给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
//
//请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>
#include <set>

using namespace std;

class Solution {
public:
    int firstMissingPositive(vector<int> &nums) {
        /**
         * 常规想法:排序 从1开始，找第几个正数不存在
         * 题目要求o(n)时间和o(1)空间
         *
         */
        unordered_set<int> s;
        for (auto &x:nums) {
            if (x > 0)
                s.insert(x);
        }
        // 枚举1到N
        int i = 1;
        for (; i <= nums.size(); ++i) {
            if (!s.count(i))
                break;
        }
        return i;
    }
    // AC 5%
};

class Solution2 { // 题解 hash
public:
    int firstMissingPositive(vector<int> &nums) {
        int n = (int) nums.size();
        for (int &num: nums) {
            // 小等于0的 标记为n+1
            if (num <= 0) {
                num = n + 1;
            }
        }
        for (int i = 0; i < n; ++i) {
            //  遍历数组 把nums[i]下标处标记为负数
            int num = abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -abs(nums[num - 1]);
            }
        }
        // 再次遍历数组  找到第一个为正数的位置
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
};

class Solution3 { // 题解 置换
public:
    int firstMissingPositive(vector<int> &nums) {
        int n = (int) nums.size();
        // 把nums[i]放到 i-1位置上去
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums[nums[i] - 1], nums[i]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
};

int main() {
    vector<int> nums{4, 2, 1, 2};
    Solution3 solution;
    cout << solution.firstMissingPositive(nums) << endl;
    return 0;
}
